package sliding_window;

import java.util.HashMap;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-01-19
 * Time:15:14
 * Text：LCR 017. 最小覆盖子串
 */
public class Text3 {

    //暴力解法+hashmap 两个for
    public static String minWindow (String S, String T) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(char a:T.toCharArray()){
            map.put(a,map.getOrDefault(a,0)+1);
        }
        int size=Integer.MAX_VALUE,start=0,jubge=0;
        char[] ary=S.toCharArray();
        for(int i=0;i+T.length()<=ary.length;i++){
            int count=0;
            HashMap<Character,Integer> map1=new HashMap<>();
            for(int k=i;k<ary.length;k++){
                map1.put(ary[k],map1.getOrDefault(ary[k],0)+1);
                if(map.getOrDefault(ary[k],0)>=map1.get(ary[k])){
                    count++;
                }
                if(count==T.length()){
                    if(size>k-i){
                        start=i;size=k-i; jubge=1;
                        break;
                    }
                }
            }
        }
        return jubge==1?S.substring(start,size+start+1):"";
    }

    //滑动窗口
    public static String minWindow2 (String S, String T) {
        HashMap<Character,Integer> map=new HashMap<>();
        for(char a:T.toCharArray()){
            map.put(a,map.getOrDefault(a,0)+1);
        }
        int size=Integer.MAX_VALUE,start=0,judge=0;
        char[] ary=S.toCharArray();
        int count=0;
        HashMap<Character,Integer> map1=new HashMap<>();
        for(int left=0,right=0;right<ary.length;right++){

            map1.put(ary[right],map1.getOrDefault(ary[right],0)+1);
            if(map.getOrDefault(ary[right],0)>=map1.get(ary[right])){
                count++;
            }
            while(count==T.length()){
                if(map.getOrDefault(ary[left],0)>=map1.get(ary[left])){
                    count--;judge=1;
                    if(size>right-left){
                        size=right-left; start=left;
                    }

                }
                map1.put(ary[left],map1.get(ary[left])-1);
                left++;
            }


        }
        return judge==1?S.substring(start,size+start+1):"";
    }


    public static void main(String[] args) {
        String str="XDOYEZODEYXNZ";
        System.out.println(str.substring(9,2+9));
        System.out.println(minWindow2("axx","ax"));
    }
}
